/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/* 
 * Copyright (c) 2009 City University of Hong Kong
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License m_version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Author: Wilson Thong (wilsonwk@ee.cityu.edu.hk) 
 */
#ifndef PACKET_REORDER_CALCULATOR_H
#define PACKET_REORDER_CALCULATOR_H

#include <vector>
#include <set>
#include <map>
#include <list>
#include "packet-reorder-calculator-tag.h"
#include "ns3/delay-jitter-estimation.h"
#include "ns3/nstime.h"
#include "ns3/packet.h"
#include "ns3/traced-callback.h"
#include "ns3/object.h"

namespace ns3 {
namespace eecityu {

using namespace std;

/**
 * \brief A calculator to calcuate various packet reodering metrics defined
 * in RFC 4737. This class is intended to augment the DelayJitterEstimation class
 *
 * The class keeps three lists of packet records on the run, a list of missing packets,
 * a list of reordered packets, and a list of duplicated packets. The 
 * expected-sequence-number-on-the-next-arrival value R is also maintained. Packets can be 
 * known to be one of the following types by using these information.
 * - Packet with sequence number s is received in order: If s < R and s is not found
 * in all the three lists.
 * - Packet s is missing: If s is found in the list of missing packets
 * - Packet s is reorder: If s is found in the list of recordered packets
 * - Packet s is duplicated: If s is found in the list of duplicated packets
 * - Packet s is not yet arrived: if s >= R.
 *
 * To maintain the correct function of this class, updating the above information must follow
 * specific rules, as described below.
 * - When packet r arrived and r == T, r is just throw away and T := r+1
 * - When packet r arrived and r > T, packets T, T+1, ..., r-1 are added into the list of 
 * missing packets. T := r+1
 * - When packet r arrived and r < T and r is found in the list of missing packets, r
 * is removed from the list of missing packets and is added into the list of reordered packets.
 * - When packet r arrived and r < T and r is not found in the list of missing packets, 
 * r is added into the list of duplicated packets.
 *
 *
 */
class PacketReorderCalculator : public Object
{
public:
  static TypeId GetTypeId (void);

  PacketReorderCalculator (void);
  virtual ~PacketReorderCalculator (void);
  /**
   * \brief Add some tags to the packets for probing packet sequence reordering
   *
   * \param packet The packet to be sent into a network
   * \return The packet sequence number
   *
   * The PrepareTx adds tags to the packet. The tags indicate packet sequence
   * number and the departure time, so that the RecordRx () can measure and
   * calculate the reordering metric
   */
  uint64_t PrepareTx (Ptr<const Packet> packet);
  /**
   * \brief Record the arrived packet for later calculating reordering metric
   *
   * \param packet The arrival packet. 
   * \return The packet sequence number
   *
   * The packet being recorded must be prepared by the PrepareTx () 
   * so that the packet will contain the necessary tags for calculating 
   * reordering metric. It any tags are missing exception is thrown
   */
  uint64_t RecordRx (Ptr<const Packet> packet);
  /**
   * \brief Record the lost packet for faster reodering metric calculation
   *
   * \param packet The dropped packet
   * \return The tag marked with the packet sequence number
   *
   * This is an optional method. If dropped packets are recorded as well,
   * some searching can be skipped and thus speeding up the reordering metric
   * calculation.
   */
  PacketReorderCalculatorTag RecordDrop (Ptr<const Packet> packet);
  /**
   * \brief Get the number Rx records
   * \return The number of recived packets, including duplicated packets, recorded so far
   */
  uint32_t GetNArrival () const;
  /**
   * \brief Get the number of duplicated packets recorded
   * \return The number of duplicated pacekts recorded so far
   */
  uint32_t GetNDuplicated () const;
  /**
   * \brief Get the number of missing packets
   * \return The number of mssing packets. These packets may be lost or may
   * late. Nevertheless, they are expected to be recorded but are missing currently
   */
  uint32_t GetNMissing () const;
  /**
   * \brief Get the number of recordered packets
   * \return The number of reordered packets
   */
  uint32_t GetNReordered () const;
  /**
   * \return Get the total number of packets sent from the source
   */
  uint64_t GetNPacketsSent () const;
  /**
   * \return Get the total bytes sent from the source
   */
  uint64_t GetNBytesSent () const;
  /**
   * \brief Query if a packet is missing
   *
   * \param s The sequence number of the packet being queried, starting from zero.
   * \return True if the packet specified by the sequence number is missing
   */
  bool IsMissing (uint64_t s) const;
  /**
   * \brief Query if a packet is Type-P-Reordered
   *
   * \param s The sequence number of the packet being queried, starting from zero.
   * \return True if the indexed packet is Type-P-Reordered; 
   * false otherwise.
   *
   * The method query if a packet is Type-P-Reordered as defined in  
   * Section 3.1 of RFC 4737. 
   *
   * The first Rx record (or the received packet recorded by RecordRx ()) has 
   * rxIndex = 0, and the subsequent packet record has rxIndex incremented by 
   * one from the its previous received packet. Thus, this rxIndex is not 
   * necessarily the sequence number coded with the packet.
   */
  bool IsReordered (uint64_t s) const;
  /**
   * \brief Query the Type-P-Packet-Reordering-Extent-Stream
   *
   * \param s The sequence number of the packet being queried, starting from zero
   * \return The Type-P-Packet-Reordering-Extent-Stream of the queried packet as defined in RFC 4737
   *
   * The method calculates the Type-P-Packet-Reordering-Extent-Stream as defined
   * in Section 4.2.1 of RFC 4737. Basically, it is the number of packets overtooken
   * by the packet this method is querying. See PacketReorderCalculator::IsReordered 
   * for the definition of rxIndex.
   *
   * Note that Type-P-Packet-Reordering-Extent-Stream is only defined for the packets
   * whose Type-P-Reordered is true. If the packet is not re-ordered, this method
   * returns zero.
   */
  uint64_t GetReorderingExtent (uint64_t s) const;
  /**
   * \brief Query the Type-P-Packet-Late-Time-Stream
   *
   * \param s The sequence number of the packet being queried, starting from zero
   * \return The Type-P-Packet-Late-Time-Stream as defined in RFC 4737
   *
   * The method calculates the Type-P-Packet-Late-Time-Stream as defined
   * in Section 4.3 of RFC 4737. Basically, it is the time the packet should
   * be delayed in order to bring this packet back to in-order. See 
   * PacketReorderCalculator::IsReordered for the definition of rxIndex. 
   *
   * Note that Type-P-Packet-Late-Time-Stream is only defined for the packets
   * whose Type-P-Reordered is true. If the packet is not re-ordered, this method
   * returns zero.
   */
  Time GetLateTime (uint64_t s) const;
  
protected:
  virtual void DoDispose (void);
private:
  /**
   * \brief Store the information for each packet arrival event
   */
  struct PacketArrivalRecord
  {
    PacketArrivalRecord ();
    /**
     * \brief Create a arrival record with sequence number
     * \param s The sequence number for this record
     */
    explicit PacketArrivalRecord (uint64_t s);

    bool operator <  (const PacketArrivalRecord& r) const;
    bool operator >  (const PacketArrivalRecord& r) const;
    bool operator == (const PacketArrivalRecord& r) const;
    bool operator != (const PacketArrivalRecord& r) const;
    bool operator <= (const PacketArrivalRecord& r) const;
    bool operator >= (const PacketArrivalRecord& r) const;

    /// The index assigned incrementally by a receiver
    uint64_t rxIndex;
    /// The packet sequence number assigned when it was sent from a transimitter
    uint64_t seqNum;
    /// The time instance when the packet is left from a transmitter
    Time txTime;
    /// The time instance when the packet arrives to a receiver
    Time rxTime;
    /// The size, in bytes, of the packet 
    uint32_t packetSize;
  };
  /**
   * \brief Add a range of sequence number into the missing record list
   * \param s1 The first sequence number to be added into the missing record list
   * \param s2 The last sequence number to be added into the missing record list
   *
   * Note that the range is from s1 to s2, both inclusive
   */
  void AddToMissingRecord (uint64_t s1, uint64_t s2);
  /**
   * \brief Add the arrival packet into the reorder record set
   * \param r The record to be added into the reorder record set
   *
   * An arrival packet that is reordered should be maintained in the 
   * reorder record set. Such packet must exists in the missing record list
   * before it can be added into the reorder record set
   */
  void AddToReorderRecord (PacketArrivalRecord r);
  /**
   * \brief Add the arrival record to the duplicated record map
   * \param r The record to be added into the reorder record map
   * \return True the arrival record is added into the duplicated
   * record map successfully; false otherwise.
   *
   * A duplicated record cannot exist in the missing record list,
   * or exception is thrown. 
   *
   * If false is returned, it indicates that the packet referred by
   * the record is not a duplicated packet
   */
  bool AddToDuplicatedRecord (PacketArrivalRecord r);
  /**
   * \brief Add an arrival packet record to the "missing range end" set
   *
   * \param r The record of an arrival packet to be added into the set
   *
   * The "missing range end" set is used for calculating the reordering extent.
   * For a reordered packet i, the packet j is needed for the calculation where 
   * it is the earliest packet received and has a larger sequence number 
   * (i.e. j.seqNum > i.seqNum). The packet j can be found in the "missing range end" set
   *
   * \see GetReorderingExtent ()
   */
  void AddToMissingRangeEnd (PacketArrivalRecord r);
  /**
   * \brief Query if a packet is Type-P-Reordered
   *
   * \param s The sequence number of the packet being queried, starting from zero.
   * \param iter The iterator pointing to the reordered packet record in the 
   * reordered record set
   *
   * This is the same as IsReordered (uint64_t s), but returns
   * an iterator pointing to the record of 's' in the reordered record set
   *
   * \see IsReordered (uint64_t s)
   */
  bool IsReordered (uint64_t s, set<PacketArrivalRecord>::iterator& iter) const;
  /**
   * \brief Query the reordering extent of a packet
   *
   * \param s The sequence of the packet whose reordering extent is being queried
   * \param s_iter Output an iterator pointing to the record of "s" in the reordererd record set
   * \param earliestUb_iter Output an iterator pointing to the "earliest upper bound" record of s
   * set in the "missing range end" set
   *
   * The method is the same as GetReorderingExtent (uint64_t s), except the two
   * output parameters
   *
   * \see GetReorderingExtent (uint64_t s)
   */
  uint64_t GetReorderingExtent (
    uint64_t s, 
    set<PacketArrivalRecord>::iterator& s_iter,
    set<PacketArrivalRecord>::iterator& earliestUb_iter) const;
  /**
   * \brief Update the states for each arrival packet recorded
   * 
   * \param arrival The record of an arrival packet
   * \param type_P_Reordered Output parameter. Return true if the arrival packet
   * is Type-P-Reordered
   * \param sequenceDiscontinuty Output parameter. Return true if there is
   * sequence discontinuity when receiving arrival packetsf
   * \param seqDiscontinutySize Output parameter. Return the number of packets
   * skipped when there exists a sequence discontinuity
   *
   * The class has several states to maintain for a proper reception of arrival packets.
   * These states include, next expected received sequence number, reception index of 
   * arrival packets, etc. These states are updated by this method for each arrival packet
   * received.
   *
   * At the same time, the methods output three variables. These variables are defined in
   * Section 3.3 and 3.4 of RFC 4737.
   */
  void UpdateRx (
    const PacketArrivalRecord& arrival,
    bool& type_P_Reordered,
    bool& sequenceDiscontinuty,
    uint64_t& seqDiscontinutySize);

  /// The sequence number expected to be in the next arrival packet
  uint64_t m_nextExp;
  /// Indicate the rxIndex to be assigned to the next coming packet
  uint64_t m_nextRxIndex;
  /// Maintain the proper sequence number for transmitting packets, starting from zero
  uint64_t m_nextTxSeqNum;
  /// To count the total number of packets sent from the session's source
  uint64_t m_totalNumPacketsSent;
  /// To count the total bytes sent from the session's source
  uint64_t m_totalBytesSent;
  /// Record the duplicated recieved packets. The second value remembers the number of duplication found
  map<PacketArrivalRecord, uint32_t> m_duplicatedRecordMap;
  /// Record the set of packets that are Type-P-Reordered
  set<PacketArrivalRecord> m_reorderRecordSet;
  /// Record the set of packets that are expected to be received but not yet arrived
  list<PacketArrivalRecord> m_missingRecordList;
  /// Set of arrival packets that immediately after a continuous range of missing packets
  set<PacketArrivalRecord> m_missingRangeEndSet;
  /// An estimation to measure packet transiting delay and to estimate delay jitter
  DelayJitterEstimation m_delayJitterEstimator;

  /// Trace source for receiving duplicated packet
  TracedCallback<> m_duplicatedPktRxTrace;
  /// Trace source for receiving a reordered packet
  TracedCallback<> m_reorderedPktRxTrace;
  /// Trace source for accessing the reordering extent of each reordered packet
  TracedCallback<uint64_t> m_reorderedExtentRxTrace;
  /// Trace source for accessing the reordering late-time of each reordered packet
  TracedCallback<Time> m_reorderedLateTimeRxTrace;
  /// Trace source for accessing the transient delay of each received packet
  TracedCallback<Time> m_transitingDelayRxTrace;
  /// Trace source for receiving a packet
  TracedCallback<> m_pktRxTrace;
  /// Trace source for transmitting a packet
  TracedCallback<> m_pktTxTrace;
};

} // namespace eecityu
} // namespace ns3


#endif //#ifndef PACKET_REORDER_CALCULATOR_H
